using System;

public class SudokuP6
{
    const int SEED = 438911343;

    ulong[] possibleMask;
    bool[] isFixed;
    int[] knownValue;
    int[][] sets;
    int[][] inSet;
    int[][] inSetIndex;
    int[][] pairEmpties;
    ulong[][] trans;
    bool[] pairEmptyNeedsRecalculating;
    bool[] setUpdated;
    ulong[] pairEmptyMask;
    int[][] pairEmptyAt;
    ulong anyMask;
    int n;
    int n2;
    int n4;
    static Random random = new Random(SEED);
    //StreamWriter log = null; 

    void startLogging()
    {
        //log = new StreamWriter("log"); 
        //log.WriteLine(n2); 
    }

    void logEvent(string ev)
    {
        //log.WriteLine(ev); 
    }

    void finishLogging()
    {
        //log.Close(); 
        //log = null; 
    }

    void assert(bool assertion)
    {
        if (!assertion)
        {
            // That's a bug!! 
            //Debug.Assert(false); 
        }
    }

    public int[] initialize(int N)
    {
        n = N;
        n2 = n * n;
        n4 = n * n * n * n;
        startLogging();
        initSets();
        initPairEmpties();
        possibleMask = new ulong[n4];
        isFixed = new bool[n4];
        knownValue = new int[n4];
        anyMask = (1Lu << (n2 - 1)) - 1 + (1Lu << (n2 - 1));
        for (int i = 0; i < possibleMask.Length; ++i)
            possibleMask[i] = anyMask;
        trans = new ulong[sets.Length][];
        for (int i = 0; i < sets.Length; ++i)
        {
            trans[i] = new ulong[n2];
            for (int j = 0; j < n2; ++j)
                trans[i][j] = anyMask;
        }
        return decide();
    }

    private void initPairEmpties()
    {
        pairEmpties = new int[4 * n * n2][];

        int last = 0;

        for (int i = 0; i < n2; ++i)
            for (int j = 0; j < n; ++j)
            {
                int top = (i / n) * n;
                int bottom = (i / n + 1) * n;

                int[] left = new int[n2 - n];
                int[] right = new int[n2 - n];

                int leftId = 0;
                for (int k = 0; k < n2; ++k)
                    if (k / n != j)
                        left[leftId++] = i * n2 + k;

                int rightId = 0;
                for (int k = 0; k < n; ++k)
                    for (int l = top; l < bottom; ++l)
                        if (l != i)
                            right[rightId++] = l * n2 + j * n + k;

                pairEmpties[last++] = left;
                pairEmpties[last++] = right;
            }

        for (int i = 0; i < n2; ++i)
            for (int j = 0; j < n; ++j)
            {
                int top = (i / n) * n;
                int bottom = (i / n + 1) * n;

                int[] left = new int[n2 - n];
                int[] right = new int[n2 - n];

                int leftId = 0;
                for (int k = 0; k < n2; ++k)
                    if (k / n != j)
                        left[leftId++] = k * n2 + i;

                int rightId = 0;
                for (int k = 0; k < n; ++k)
                    for (int l = top; l < bottom; ++l)
                        if (l != i)
                            right[rightId++] = (j * n + k) * n2 + l;

                pairEmpties[last++] = left;
                pairEmpties[last++] = right;
            }

        assert(last == pairEmpties.Length);

        pairEmptyMask = new ulong[4 * n * n2];
        pairEmptyAt = new int[n4][];

        for (int i = 0; i < n4; ++i)
            pairEmptyAt[i] = new int[4 * (n - 1)];

        int[] pairEmptyAtPos = new int[n4];

        for (int i = 0; i < pairEmpties.Length; ++i)
        {
            pairEmptyMask[i] = anyMask;
            int[] pairEmpty = pairEmpties[i];
            foreach (int id in pairEmpty)
                pairEmptyAt[id][pairEmptyAtPos[id]++] = i;
        }

        for (int i = 0; i < n4; ++i)
            assert(pairEmptyAtPos[i] == pairEmptyAt[i].Length);

        pairEmptyNeedsRecalculating = new bool[pairEmpties.Length];
    }

    int countBits(ulong a)
    {
        int res = 0;
        while (a > 0)
        {
            a = a & (a - 1);
            ++res;
        }
        return res;
    }

    int lowestBit(ulong a)
    {
        if (a == 0)
            return -1;
        int res = 0;
        while ((a & 1) == 0)
        {
            ++res;
            a >>= 1;
        }
        return res;
    }

    private int[] decide()
    {
        double best = -1;
        int bestId = -1;
        for (int i = 0; i < n4; ++i)
            if (!isFixed[i])
            {
                double cur = getRating(i);
                if (cur > best)
                {
                    best = cur;
                    bestId = i;
                }
            }

        if (bestId < 0)
        {
            finishLogging();
            int[] res = new int[n4];
            for (int i = 0; i < n4; ++i)
                res[i] = knownValue[i] + 1;
            return res;
        }
        else
        {
            return new int[] { bestId / n2 + 1, bestId % n2 + 1 };
        }
    }

    private double getRating(int id)
    {
        int x = id / n2;
        int y = id % n2;
        double res = n * 3 * countBits(possibleMask[id]) + x + y + random.NextDouble();
        return res;
    }

    private void initSets()
    {
        sets = new int[3 * n2][];
        inSet = new int[n4][];
        inSetIndex = new int[n4][];

        for (int i = 0; i < n4; ++i)
        {
            inSet[i] = new int[3];
            inSetIndex[i] = new int[3];
        }

        int last = 0;
        int[] lastIn = new int[n4];

        for (int i = 0; i < n2; ++i)
        {
            sets[last] = new int[n2];
            int cur = i * n2;
            for (int j = 0; j < n2; ++j)
            {
                sets[last][j] = cur;
                inSetIndex[cur][lastIn[cur]] = j;
                inSet[cur][lastIn[cur]++] = last;
                ++cur;
            }
            ++last;
        }

        for (int i = 0; i < n2; ++i)
        {
            sets[last] = new int[n2];
            int cur = i;
            for (int j = 0; j < n2; ++j)
            {
                sets[last][j] = cur;
                inSetIndex[cur][lastIn[cur]] = j;
                inSet[cur][lastIn[cur]++] = last;
                cur += n2;
            }
            ++last;
        }

        for (int i1 = 0; i1 < n; ++i1)
            for (int i2 = 0; i2 < n; ++i2)
            {
                sets[last] = new int[n2];
                int cur = i1 * n * n2 + i2 * n;
                for (int j = 0; j < n2; ++j)
                {
                    sets[last][j] = cur;
                    inSetIndex[cur][lastIn[cur]] = j;
                    inSet[cur][lastIn[cur]++] = last;
                    if (j % n == (n - 1))
                        cur += (n2 - n + 1);
                    else
                        ++cur;
                }
                ++last;
            }

        setUpdated = new bool[sets.Length];

        assert(last == sets.Length);

        for (int i = 0; i < n4; ++i)
            assert(lastIn[i] == inSet[i].Length);
    }



    public int[] queryResults(int x, int[] query)
    {
        //logEvent("1 " + query[0] + " " + query[1] + " " + x); 
        --x;
        int q = (query[0] - 1) * n2 + query[1] - 1;

        gotKnowledge(q, x);

        derive();

        return decide();
    }

    private void gotKnowledge(int position, int value)
    {
        //logEvent("2 " + (position / n2 + 1) + " " + (position % n2 + 1) + " " + (value + 1)); 
        possibleMask[position] = 1Lu << value;
        cellUpdated(position);
        isFixed[position] = true;
        knownValue[position] = value;

        ulong mask = ~(1Lu << value);

        foreach (int setId in inSet[position])
        {
            foreach (int item in sets[setId])
            {
                if (item != position)
                    if ((possibleMask[item] & mask) != possibleMask[item])
                    {
                        possibleMask[item] &= mask;
                        cellUpdated(item);
                    }
            }
        }
    }

    private void derive()
    {
        ulong[] tmp = new ulong[n2 + 1];
        int[,] was = new int[n2, n2];
        int[, ,] was3 = new int[n2, n2, n2];
        for (int i = 0; i < n2; ++i)
            for (int j = 0; j < n2; ++j)
                was[i, j] = -1;

        bool updated;
        do
        {
            do
            {
                updated = false;
                for (int i = 0; i < n4; ++i)
                    if (!isFixed[i])
                    {
                        // Singles 

                        ulong mask = possibleMask[i];
                        if ((mask & (mask - 1)) == 0)
                        {
                            int x = lowestBit(mask);
                            gotKnowledge(i, x);
                            updated = true;
                        }
                    }

                for (int index = 0; index < sets.Length; ++index)
                    if (setUpdated[index])
                    {
                        // Hidden singles 

                        setUpdated[index] = false;
                        int[] curSet = sets[index];

                        tmp[n2] = 0;
                        for (int i = n2 - 1; i >= 0; --i)
                        {
                            tmp[i] = possibleMask[curSet[i]] | tmp[i + 1];
                        }
                        ulong cur = 0;
                        for (int i = 0; i < n2; ++i)
                        {
                            ulong mask = cur | tmp[i + 1];
                            int curAt = curSet[i];
                            ulong cmask = possibleMask[curAt];
                            cur |= cmask;
                            if (!isFixed[curAt] && (cmask & mask) != cmask)
                            {
                                cmask &= ~mask;
                                assert(cmask != 0 && (cmask & (cmask - 1)) == 0);
                                int x = lowestBit(cmask);
                                gotKnowledge(curAt, x);
                                updated = true;
                                break;
                            }
                        }

                        // Naked pairs 

                        ulong foundMask = 0;
                        bool any = false;
                        int i1 = -1;
                        int i2 = -1;

                        for (int i = 0; i < n2; ++i)
                        {
                            int curAt = curSet[i];
                            if (isFixed[curAt])
                                continue;
                            ulong cmask = possibleMask[curAt];
                            if (cmask == 0)
                                continue;
                            ulong tmpMask = cmask & (cmask - 1);
                            if (tmpMask == 0 || (tmpMask & (tmpMask - 1)) != 0)
                                continue;

                            int b1 = lowestBit(cmask ^ tmpMask);
                            int b2 = lowestBit(tmpMask);

                            int ii = was[b1, b2];
                            if (ii >= 0)
                            {
                                foundMask = cmask;
                                i1 = curAt;
                                i2 = ii;
                                any = true;
                                break;
                            }
                            else
                                was[b1, b2] = curAt;
                        }

                        for (int i = 0; i < n2; ++i)
                        {
                            int curAt = curSet[i];
                            if (isFixed[curAt])
                                continue;
                            ulong cmask = possibleMask[curAt];
                            if (cmask == 0)
                                continue;
                            ulong tmpMask = cmask & (cmask - 1);
                            if (tmpMask == 0 || (tmpMask & (tmpMask - 1)) != 0)
                                continue;

                            int b1 = lowestBit(cmask ^ tmpMask);
                            int b2 = lowestBit(tmpMask);

                            was[b1, b2] = -1;
                        }

                        if (any)
                        {
                            ulong mask = ~foundMask;
                            foreach (int id in curSet)
                                if (id != i1 && id != i2)
                                    if ((possibleMask[id] & mask) != possibleMask[id])
                                    {
                                        possibleMask[id] &= mask;
                                        cellUpdated(id);
                                        updated = true;
                                    }
                        }

                        // Naked triples 

                        foundMask = 0;
                        any = false;
                        i1 = -1;
                        i2 = -1;
                        int i3 = -1;

                        for (int i = 0; i < n2; ++i)
                        {
                            int curAt = curSet[i];
                            if (isFixed[curAt])
                                continue;
                            ulong cmask = possibleMask[curAt];
                            if (cmask == 0)
                                continue;
                            ulong tmpMask = cmask & (cmask - 1);
                            if (tmpMask == 0)
                                continue;
                            ulong tmpMask2 = tmpMask & (tmpMask - 1);
                            if (tmpMask2 != 0 && (tmpMask2 & (tmpMask2 - 1)) != 0)
                                continue;

                            int b1 = lowestBit(cmask ^ tmpMask ^ tmpMask2);
                            int b2 = lowestBit(tmpMask ^ tmpMask2);
                            int b3 = lowestBit(tmpMask2);

                            if (b3 >= 0)
                            {
                                int ii = was3[b1, b2, b3];
                                ii <<= 8;
                                ii |= (i + 1);
                                was3[b1, b2, b3] = ii;
                                if (ii >= (1 << 16))
                                {
                                    foundMask = cmask;
                                    i1 = (ii >> 16) - 1;
                                    i2 = ((ii >> 8) & 0xFF) - 1;
                                    i3 = (ii & 0xFF) - 1;
                                    any = true;
                                    break;
                                }
                            }
                            else
                            {
                                for (b3 = n2 - 1; b3 > b2; --b3)
                                {
                                    int ii = was3[b1, b2, b3];
                                    ii <<= 8;
                                    ii |= (i + 1);
                                    was3[b1, b2, b3] = ii;
                                    if (ii >= (1 << 16))
                                    {
                                        foundMask = cmask;
                                        i1 = (ii >> 16) - 1;
                                        i2 = ((ii >> 8) & 0xFF) - 1;
                                        i3 = (ii & 0xFF) - 1;
                                        any = true;
                                        break;
                                    }
                                }
                                if (any)
                                    break;

                                for (b2 = b2 - 1; b2 > b1; --b2)
                                {
                                    int ii = was3[b1, b2, b3];
                                    ii <<= 8;
                                    ii |= (i + 1);
                                    was3[b1, b2, b3] = ii;
                                    if (ii >= (1 << 16))
                                    {
                                        foundMask = cmask;
                                        i1 = (ii >> 16) - 1;
                                        i2 = ((ii >> 8) & 0xFF) - 1;
                                        i3 = (ii & 0xFF) - 1;
                                        any = true;
                                        break;
                                    }
                                }

                                if (any)
                                    break;

                                for (b1 = b1 - 1; b1 >= 0; --b1)
                                {
                                    int ii = was3[b1, b2, b3];
                                    ii <<= 8;
                                    ii |= (i + 1);
                                    was3[b1, b2, b3] = ii;
                                    if (ii >= (1 << 16))
                                    {
                                        foundMask = cmask;
                                        i1 = (ii >> 16) - 1;
                                        i2 = ((ii >> 8) & 0xFF) - 1;
                                        i3 = (ii & 0xFF) - 1;
                                        any = true;
                                        break;
                                    }
                                }

                                if (any)
                                    break;
                            }
                        }

                        for (int i = 0; i < n2; ++i)
                        {
                            int curAt = curSet[i];
                            if (isFixed[curAt])
                                continue;
                            ulong cmask = possibleMask[curAt];
                            if (cmask == 0)
                                continue;
                            ulong tmpMask = cmask & (cmask - 1);
                            if (tmpMask == 0)
                                continue;
                            ulong tmpMask2 = tmpMask & (tmpMask - 1);
                            if (tmpMask2 != 0 && (tmpMask2 & (tmpMask2 - 1)) != 0)
                                continue;

                            int b1 = lowestBit(cmask ^ tmpMask ^ tmpMask2);
                            int b2 = lowestBit(tmpMask ^ tmpMask2);
                            int b3 = lowestBit(tmpMask2);

                            if (b3 >= 0)
                                was3[b1, b2, b3] = 0;
                            else
                            {
                                for (b3 = n2 - 1; b3 > b2; --b3)
                                    was3[b1, b2, b3] = 0;
                                for (b2 = b2 - 1; b2 > b1; --b2)
                                    was3[b1, b2, b3] = 0;
                                for (b1 = b1 - 1; b1 >= 0; --b1)
                                    was3[b1, b2, b3] = 0;
                            }
                        }

                        if (any)
                        {
                            ulong mask = ~foundMask;
                            for (int i = 0; i < n2; ++i)
                                if (i != i1 && i != i2 && i != i3)
                                {
                                    int id = curSet[i];
                                    if ((possibleMask[id] & mask) != possibleMask[id])
                                    {
                                        possibleMask[id] &= mask;
                                        cellUpdated(id);
                                        updated = true;
                                    }
                                }
                        }

                        // Hidden pairs 

                        ulong[] curTrans = trans[index];

                        any = false;
                        foundMask = 0;
                        i1 = -1;
                        i2 = -1;

                        for (int i = 0; i < n2; ++i)
                        {
                            ulong cmask = curTrans[i];
                            if (cmask == 0)
                                continue;
                            ulong tmpMask = cmask & (cmask - 1);
                            if (tmpMask == 0 || (tmpMask & (tmpMask - 1)) != 0)
                                continue;

                            int b1 = lowestBit(cmask ^ tmpMask);
                            int b2 = lowestBit(tmpMask);

                            int ii = was[b1, b2];
                            if (ii >= 0)
                            {
                                foundMask = (1Lu << ii) | (1Lu << i);
                                i1 = b1;
                                i2 = b2;
                                any = true;
                                break;
                            }
                            else
                                was[b1, b2] = i;
                        }

                        for (int i = 0; i < n2; ++i)
                        {
                            ulong cmask = curTrans[i];
                            if (cmask == 0)
                                continue;
                            ulong tmpMask = cmask & (cmask - 1);
                            if (tmpMask == 0 || (tmpMask & (tmpMask - 1)) != 0)
                                continue;

                            int b1 = lowestBit(cmask ^ tmpMask);
                            int b2 = lowestBit(tmpMask);

                            was[b1, b2] = -1;
                        }

                        if (any)
                        {
                            ulong mask = foundMask;
                            int id = curSet[i1];
                            if ((possibleMask[id] & mask) != possibleMask[id])
                            {
                                possibleMask[id] &= mask;
                                cellUpdated(id);
                                updated = true;
                            }
                            id = curSet[i2];
                            if ((possibleMask[id] & mask) != possibleMask[id])
                            {
                                possibleMask[id] &= mask;
                                cellUpdated(id);
                                updated = true;
                            }
                        }

                        // Hidden triples 

                        curTrans = trans[index];
                        foundMask = 0;
                        any = false;
                        i1 = -1;
                        i2 = -1;
                        i3 = -1;

                        for (int i = 0; i < n2; ++i)
                        {
                            ulong cmask = curTrans[i];
                            if (cmask == 0)
                                continue;
                            ulong tmpMask = cmask & (cmask - 1);
                            if (tmpMask == 0)
                                continue;
                            ulong tmpMask2 = tmpMask & (tmpMask - 1);
                            if (tmpMask2 != 0 && (tmpMask2 & (tmpMask2 - 1)) != 0)
                                continue;

                            int b1 = lowestBit(cmask ^ tmpMask ^ tmpMask2);
                            int b2 = lowestBit(tmpMask ^ tmpMask2);
                            int b3 = lowestBit(tmpMask2);

                            if (b3 >= 0)
                            {
                                int ii = was3[b1, b2, b3];
                                ii <<= 8;
                                ii |= (i + 1);
                                was3[b1, b2, b3] = ii;
                                if (ii >= (1 << 16))
                                {
                                    i1 = (ii >> 16) - 1;
                                    i2 = ((ii >> 8) & 0xFF) - 1;
                                    i3 = (ii & 0xFF) - 1;
                                    foundMask = (1Lu << i1) | (1Lu << i2) | (1Lu << i3);
                                    i1 = b1;
                                    i2 = b2;
                                    i3 = b3;
                                    any = true;
                                    break;
                                }

                            }
                            else
                            {
                                for (b3 = n2 - 1; b3 > b2; --b3)
                                {
                                    int ii = was3[b1, b2, b3];
                                    ii <<= 8;
                                    ii |= (i + 1);
                                    was3[b1, b2, b3] = ii;
                                    if (ii >= (1 << 16))
                                    {
                                        i1 = (ii >> 16) - 1;
                                        i2 = ((ii >> 8) & 0xFF) - 1;
                                        i3 = (ii & 0xFF) - 1;
                                        foundMask = (1Lu << i1) | (1Lu << i2) | (1Lu << i3);
                                        i1 = b1;
                                        i2 = b2;
                                        i3 = b3;
                                        any = true;
                                        break;
                                    }

                                }
                                if (any)
                                    break;

                                for (b2 = b2 - 1; b2 > b1; --b2)
                                {
                                    int ii = was3[b1, b2, b3];
                                    ii <<= 8;
                                    ii |= (i + 1);
                                    was3[b1, b2, b3] = ii;
                                    if (ii >= (1 << 16))
                                    {
                                        i1 = (ii >> 16) - 1;
                                        i2 = ((ii >> 8) & 0xFF) - 1;
                                        i3 = (ii & 0xFF) - 1;
                                        foundMask = (1Lu << i1) | (1Lu << i2) | (1Lu << i3);
                                        i1 = b1;
                                        i2 = b2;
                                        i3 = b3;
                                        any = true;
                                        break;
                                    }

                                }

                                if (any)
                                    break;

                                for (b1 = b1 - 1; b1 >= 0; --b1)
                                {
                                    int ii = was3[b1, b2, b3];
                                    ii <<= 8;
                                    ii |= (i + 1);
                                    was3[b1, b2, b3] = ii;
                                    if (ii >= (1 << 16))
                                    {
                                        i1 = (ii >> 16) - 1;
                                        i2 = ((ii >> 8) & 0xFF) - 1;
                                        i3 = (ii & 0xFF) - 1;
                                        foundMask = (1Lu << i1) | (1Lu << i2) | (1Lu << i3);
                                        i1 = b1;
                                        i2 = b2;
                                        i3 = b3;
                                        any = true;
                                        break;
                                    }

                                }

                                if (any)
                                    break;
                            }
                        }

                        for (int i = 0; i < n2; ++i)
                        {
                            ulong cmask = curTrans[i];
                            if (cmask == 0)
                                continue;
                            ulong tmpMask = cmask & (cmask - 1);
                            if (tmpMask == 0)
                                continue;
                            ulong tmpMask2 = tmpMask & (tmpMask - 1);
                            if (tmpMask2 != 0 && (tmpMask2 & (tmpMask2 - 1)) != 0)
                                continue;

                            int b1 = lowestBit(cmask ^ tmpMask ^ tmpMask2);
                            int b2 = lowestBit(tmpMask ^ tmpMask2);
                            int b3 = lowestBit(tmpMask2);

                            if (b3 >= 0)
                                was3[b1, b2, b3] = 0;
                            else
                            {
                                for (b3 = n2 - 1; b3 > b2; --b3)
                                    was3[b1, b2, b3] = 0;
                                for (b2 = b2 - 1; b2 > b1; --b2)
                                    was3[b1, b2, b3] = 0;
                                for (b1 = b1 - 1; b1 >= 0; --b1)
                                    was3[b1, b2, b3] = 0;
                            }
                        }

                        if (any)
                        {
                            ulong mask = foundMask;
                            int id = curSet[i1];
                            if ((possibleMask[id] & mask) != possibleMask[id])
                            {
                                possibleMask[id] &= mask;
                                cellUpdated(id);
                                updated = true;
                            }
                            id = curSet[i2];
                            if ((possibleMask[id] & mask) != possibleMask[id])
                            {
                                possibleMask[id] &= mask;
                                cellUpdated(id);
                                updated = true;
                            }
                            id = curSet[i3];
                            if ((possibleMask[id] & mask) != possibleMask[id])
                            {
                                possibleMask[id] &= mask;
                                cellUpdated(id);
                                updated = true;
                            }
                        }
                    }
            } while (updated);

            for (int index = 0; index < pairEmpties.Length; ++index)
                if (pairEmptyNeedsRecalculating[index])
                {
                    pairEmptyNeedsRecalculating[index] = false;
                    int anotherIndex = index ^ 1;
                    ulong mask = 0;
                    foreach (int id in pairEmpties[index])
                        mask |= possibleMask[id];
                    foreach (int id in pairEmpties[anotherIndex])
                        if ((possibleMask[id] & mask) != possibleMask[id])
                        {
                            possibleMask[id] &= mask;
                            cellUpdated(id);
                            updated = true;
                        }
                }
        } while (updated);
    }

    private void cellUpdated(int id)
    {
        foreach (int pairEmptyId in pairEmptyAt[id])
            pairEmptyNeedsRecalculating[pairEmptyId] = true;

        foreach (int setId in inSet[id])
            setUpdated[setId] = true;

        for (int i = 0; i < inSet[id].Length; ++i)
        {
            int curSetId = inSet[id][i];
            int curSetAt = inSetIndex[id][i];

            ulong cmask = possibleMask[id];

            for (int j = 0; j < n2; ++j)
            {
                if ((cmask & 1) != 0)
                    trans[curSetId][j] |= (1Lu << curSetAt);
                else
                    trans[curSetId][j] &= ~(1Lu << curSetAt);
                cmask >>= 1;
            }
        }
    }
}
